package demo1;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: WHY
 * Date: 2022-12-20
 * Time: 22:45
 */
public class TestDemo {//用栈实现反转链表
    import java.util.*;
    public class Solution {
        public ListNode ReverseList(ListNode head) {
            //采用入栈出栈的方式
            //1.首先创建一个栈，并且将元素都放入栈中
            Stack<ListNode> stack=new Stack<>();
            while(head!=null){
                stack.push(head);
                head=head.next;
            }
            if(stack.isEmpty()){
                return null;
            }
            ListNode node=stack.pop();
            //将栈顶元素设为头结点
            ListNode ret=node;
            //出栈
            while(!stack.isEmpty()){
                ListNode tmpNode=stack.pop();
                node.next=tmpNode;
                node=node.next;
            }
            node.next=null;//将头结点下一个元素置为空，防止构成环
            return ret;



        }
    }

}
